package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/05fed41805ae4394ab6607d0d745c8e4?tpId=117&&tqId=37801&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking">
 * NC35 最小编辑代价</a>
 *
 * @author or2
 * @Description 给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。
 * @create 2021年09月07日 时间: 15:04
 */
public class MinEditCost {
    /**
     * min edit cost
     *
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic   int整型 insert cost
     * @param dc   int整型 delete cost
     * @param rc   int整型 replace cost
     * @return int整型
     */
    public int minEditCost(String str1, String str2, int ic, int dc, int rc) {
//        变量初始化
        int primaryLength = str1.length();
        int toLength = str2.length();
        int[][] dp = new int[primaryLength + 1][toLength + 1];
//        "" -> toStr的权值
        for (int i = 0; i <= toLength; i++) {
            dp[0][i] = ic * i;
        }
//        primaryStr -> "" 的权值
        for (int i = 0; i <= primaryLength; i++) {
            dp[i][0] = dc * i;
        }
//        双重循环
        for (int i = 1; i <= primaryLength; i++) {
            for (int j = 1; j <= toLength; j++) {
//                修改代价
                int modCost;
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    modCost = dp[i - 1][j - 1];
                } else {
                    modCost = dp[i - 1][j - 1] + rc;
                }
//                添加代价
                int insertCost = dp[i][j - 1] + ic;
//                删除代价
                int delCost = dp[i - 1][j] + dc;
//                取最小代价
                dp[i][j] = Math.min(modCost, Math.min(insertCost, delCost));
            }
        }

        return dp[primaryLength][toLength];
    }
}
